Type TList
	Field h.tLink
	Field t.tLink
End Type

Type tLink
	Field l.TList
	Field v$
End Type

Function New_List():Return Handle(New TList):End Function
Function TList.TList(list) Return Object.TList(list) End Function
Function TLink.tLink(link):Return Object.tLink(link):End Function

Function Link_Value$(link):Local lnk.tLink=TLink(link):Return lnk\v:End Function
Function SetLink_Value(link,value$):Local lnk.tLink=TLink(link):lnk\v=value:End Function

Function Add_First(list, value$)
	Local l.TList=TList(list)
	Local lnk.tLink=New tLink
	lnk\l=l
	lnk\v=value
	If l\h=Null : l\h=lnk
	Else : Insert lnk Before l\h
	EndIf
	l\h=lnk
	Return Handle(lnk)
End Function
Function Add_Last(list, value$)
	Local l.TList=TList(list)
	Local lnk.tLink=New tLink
	lnk\l=l
	lnk\v=value
	If l\h=Null : l\h=lnk
	Else : Insert lnk After l\t
	EndIf
	l\t=lnk
	Return Handle(lnk)
End Function
Function Insert_Before(link1,link2)
	Local l1.tLink=TLink(link1)
	Local l2.tLink=TLink(link2)
	If l1\l<>l2\l Then Return False
	If l1=l2 Then Return True
	Local l.TList=l1\l
	If l1=l\t Then l\t=Before l1
	If l2=l\h Then l\h=l1
	Insert l1 Before l2
	Return True
End Function
Function Insert_After(link1,link2)
	Local l1.tLink=TLink(link1)
	Local l2.tLink=TLink(link2)
	If l1\l<>l2\l Then Return False
	If l1=l2 Then Return True
	Local l.TList=l1\l
	If l1=l\h Then l\h=After l1
	If l2=l\t Then l\t=l1
	Insert l1 After l2
	Return True
End Function

Function List_First(list) :Local l.TList=TList(list):Return Handle(l\h):End Function
Function List_Last(list) :Local l.TList=TList(list):Return Handle(l\t):End Function
Function After_Link(link)
	Local lnk.tLink=TLink(link)
	If lnk=lnk\l\t Then Return 0
	Return Handle(After lnk)
End Function
Function Before_Link(link)
	Local lnk.tLink=TLink(link)
	If lnk=lnk\l\h Then Return 0
	Return Handle(Before lnk)
End Function

Function Delete_Link(link)
	Local lnk.tLink=TLink(link)
	If lnk=lnk\l\h
		If lnk=lnk\l\t
			lnk\l\h=Null
			lnk\l\t=Null
		Else
			lnk\l\h=After lnk
		EndIf
	Else
		If lnk=lnk\l\t
			lnk\l\t=Before lnk
		EndIf
	EndIf
	Delete lnk
End Function

Function Delete_List(list)
	Local l.TList=TList(list)
	Local lnk1.tLink=l\h, lnk2.tLink
	While lnk1<>Null
		If lnk1=l\t Then Delete lnk1:Exit
		lnk2=lnk1 : lnk1=After lnk1 : Delete lnk2
	Wend
	Delete l
End Function

Function Sort_List(list, sens)
	If sens<0 Then Return Sort_ListDESC(list)
	Return Sort_ListASC(list)
End Function

Function Sort_ListASC(list)
	
	If List_First(list)=List_Last(list) Then Return
	
	Local done=False
	While Not(done)
		done=True
		Local l1=After_Link(List_First(list)), l2
		While l1<>0
			l2=After_Link(l1)
			
			Local l3=Before_Link(l1), l4
			While l3<>0
				l4=Before_Link(l3)
				If Compare_String(Link_Value(l1),Link_Value(l3))<0
					Insert_Before (l1,l3)
					done=False
				EndIf
				l3=l4
			Wend
			
			l1=l2
		Wend
	Wend
	Return
	
End Function

Function Sort_ListDESC(list)
	
	If List_First(list)=List_Last(list) Then Return
	
	Local done=False
	While Not(done)
		done=True
		Local l1=Before_Link(List_Last(list)), l2
		While l1<>0
			l2=Before_Link(l1)
			
			Local l3=After_Link(l1), l4
			While l3<>0
				l4=After_Link(l3)
				If StrCompare(Link_Value(l1),Link_Value(l3))<0
				;If Compare_String(Link_Value(l1),Link_Value(l3))<0
					Insert_After (l1,l3)
					done=False
				EndIf
				l3=l4
			Wend
			
			l1=l2
		Wend
	Wend
	Return
	
End Function

Function Compare_String(v1$,v2$)
	Local ln=Len(v1):If Len(v2)<ln Then ln=Len(v2)
	For n=1 To ln
		Local c1=Asc(Mid(v1,n,1))
		Local c2=Asc(Mid(v2,n,1))
		If c1<>c2 Then Return -1+2*(c1>c2)
	Next
	If Len(v1)>ln Then Return +1
	If Len(v2)>ln Then Return -1
	Return 0
End Function



Function Print_dllList(List,x=0,y=0)
	Local l1=ListFirst(List)
	Local h=0
	While l1<>0
		Locate x,y+h : Print "   * "+LinkValue(l1) : h=h+13
		l1=AfterLink(l1)
	Wend
End Function

Function Print_b3dList(List,x=0,y=0)
	Local l1=List_First(List)
	Local h=0
	While l1<>0
		Locate x,y+h : Print "   * "+Link_Value(l1) : h=h+13
		l1=After_Link(l1)
	Wend
End Function



Local test, CountObjects, sens=-1, n
For test = 1 To 2
	
	Select test
	Case 1:CountObjects=19
	Case 2:CountObjects=500
	End Select
	Cls
	Locate 0,0
	
	Local list1=NewList()
		SeedRnd 1
		For n=1 To CountObjects
			AddLast(list1,"Objet "+Str(Rand(1,10000)))
		Next
		Local t0=MilliSecs()
		SortList list1,sens
		Local t1=MilliSecs()
	
	Local list2=New_List()
		SeedRnd 1
		For n=1 To CountObjects
			Add_Last(list2,"Objet "+Str(Rand(1,10000)))
		Next
		Local t2=MilliSecs()
		Sort_List list2,sens
		Local t3=MilliSecs()
	
	Select test
		Case 1
			Locate 000,000 : Print "   - dll list -"
			Print_dllList(list1,000,013)
			Locate 200,000 : Print "   - b3d list -"
			Print_b3dList(list2,200,013)
		Case 2
			Print " - Objetcs sorted : '"+CountObjects+"'"
			Print " "
			Print " - Time to sort Lists :"
			Print " "
			Print "    * dllList : "+(t1-t0)+" ms"
			Print "    * b3dList : "+(t3-t2)+" ms"
	End Select
	Print ""
	Print ""
	Print "              - Hit any key -"
	FlushKeys():WaitKey()
	
Next

WaitKey
End

;~IDEal Editor Parameters:
;~F#11#1C#27#32#40#45#4B#5C#66#6B#87#A4#B2#BB
;~C#Blitz3D